

/**
 * 
 * RBTree
 * 
 * An implementation of a Red Black Tree with
 * non-negative, distinct integer values
 * 
 */
public class RBTree {
//////////////////////////////// Tree fields //////////////////////////////////////////
	
	private RBNode Root = null; //this holds the pointer to the root
	

	//////////////////////////////// constructors getters & setters ///////////////////////
	
	public RBTree(RBNode parent, RBNode left, RBNode right, int key, String color){
		this.Root = new RBNode(parent, left, right, key, color);
	}
	
	
	//tree constructor
	public RBTree() {
		Root = new RBNode(); ///sets the root's parent to be a nullNode
							 //Basically the root keeps a nullNode pointing to the root node
		RBNode RootSon = new RBNode();  //sets the root node to nullNode
		Root.setLeft(RootSon);
	}

	//sets a new root for the tree
	public void setRoot(RBNode newroot){
		newroot.setParent(Root);   //sets the new node's parent field to the root's nullNode
		Root.setLeft(newroot);     //sets the nullNode's left child to be the new node
		
	}
	
	//returns the root node
	public RBNode getRoot(){
		return Root.getLeft();
	}
	
   /**
    * public boolean empty()
    * 
    * returns true if and only if the tree is empty
    *  
    * preconditions: none
    * postcondition: none
    */
   public boolean empty()
   {
	   if (Root.getLeft().nullNode())
			return true;
		else
			return false;
   }

	// returns the node with the searched key or null if not exist
	public static RBNode treeSearch(RBNode tree, int key){
		if (tree.nullNode())
			return null;
		else {
			if (key==tree.getKey())
				return tree;
			else
				if ((key<tree.getKey()))
					return treeSearch(tree.getLeft(),key);
				else
					return treeSearch(tree.getRight(),key); 
		}
	}
   /**
    * public boolean contains(int i)
    * 
    * returns true if and only if the tree contains i
    *  
    * preconditions: none
    * postcondition: none
    */
   public boolean contains(int i)
   {
	   if (treeSearch(this.getRoot(),i)==null)
		   return false;
	   else
		   return true;
   }

  
   //Inserts a new node into the tree
   public static void treeInsert(RBTree Tree, RBNode Node){
		if (Tree.empty())
			Tree.setRoot(Node);
		else {
			RBNode y = null;
			RBNode x = Tree.getRoot();
			while (!x.nullNode()){
				y = x;
				if (Node.getKey() < x.getKey())
					x = x.getLeft();
				else
					x = x.getRight();
			}
			Node.setParent(y);
			if (Node.getKey() < y.getKey())
				y.setLeft(Node);
			else
				y.setRight(Node);
		}
	}
   
   
   /**
    * public void insert(int i)
    * 
    * inserts the integer i into the binary tree; the tree
    * must remain valid (keep its invariants).
    * 
    * precondition:  contains(i) == false (that is, i is not in the tree)
    * postcondition: contains(i) == true (that is, i is in the tree)
    */
   public void insert(int i)
   {
	   RBNode temp;
	   RBNode newNode = new RBNode(null,null,null,i,"red");
	   RBNode leftNull = new RBNode(); //left nullNode nullNode
	   leftNull.setParent(newNode);
	   RBNode rightNull = new RBNode();//right nullNode
	   rightNull.setParent(newNode);
	   newNode.setRight(rightNull);
	   newNode.setLeft(leftNull);
	   
	   treeInsert(this,newNode); 

	   while ((!newNode.isRoot()) && (newNode.getParent().getColor() == "red")){  //the & may cause problems if parent is null !!!!
		   if (newNode.getParent() == newNode.getGParent().getLeft()){
			   temp = newNode.getGParent().getRight();
			   if ((!temp.nullNode()) && (temp.getColor() == "red")){      //THERE WAS A PROBLEM ON CHECKING A NULL NODE!!!!!!
				   newNode.getParent().setColor("black");           		//case1
				   temp.setColor("black");							   		//case1
				   newNode.getGParent().setColor("red");  					//case1
				   newNode = newNode.getGParent();        					//case1 
			   }
			   else {
				   if (newNode == newNode.getParent().getRight()){  
				   	  		newNode = newNode.getParent();                  //case2
				   	  		newNode.leftRotate();						    //case2
				   }
				   newNode.getParent().setColor("black");           	 	//case3
				   newNode.getGParent().setColor("red");   					//case3
				   newNode.getGParent().rightRotate();
			   }
		   }
		   else{
			   temp = newNode.getGParent().getLeft();
			   if ((!temp.nullNode()) && (temp.getColor() == "red")){
				   newNode.getParent().setColor("black");           		//case1
				   temp.setColor("black");							   		//case1
				   newNode.getGParent().setColor("red");  					//case1
				   newNode = newNode.getGParent();        					//case1
			   } 
			   else {
				   if (newNode == newNode.getParent().getLeft()){  
					   newNode = newNode.getParent();                   	//case2
					   newNode.rightRotate();						      	//case2
				   }
				   newNode.getParent().setColor("black");           		//case3
				   newNode.getGParent().setColor("red");    				//case3
				   newNode.getGParent().leftRotate();
			   }
		   }
   }
	   this.setRoot(newNode.findRoot()); // update if the root was changed
	   this.getRoot().setColor("black");
   }
  
   //RB-Delete-FIXUP
   //the method is called if a black node is deleted in the tree
   public void RBDeleteFIXUP(RBNode node){
	   RBNode temp = new RBNode();
	   
	   while ((node != getRoot()) && (node.getColor() == "black")){
		   if (node == node.getParent().getLeft()){
			   temp = node.getParent().getRight();
			   if (temp.getColor() == "red"){
				   temp.setColor("black");
				   node.getParent().setColor("red");
				   node.getParent().leftRotate();
				   temp = node.getParent().getRight();
			   }
			   if ((temp.getLeft().getColor() == "black") & (temp.getRight().getColor() == "black")){
				   temp.setColor("red");
				   node = node.getParent(); 
			   }
			   else{
				   if (temp.getRight().getColor() == "black"){
					   temp.getLeft().setColor("black");
					   temp.setColor("red");
					   temp.rightRotate();
					   temp = node.getParent().getRight();
				   }
				   temp.setColor(node.getParent().getColor());
				   node.getParent().setColor("black");
				   temp.getRight().setColor("black");
				   node.getParent().leftRotate();
				   node = getRoot();
			   }
		   }
		   else{
			   temp = node.getParent().getLeft();
			   if (temp.getColor() == "red"){
				   temp.setColor("black");
				   node.getParent().setColor("red");
				   node.getParent().rightRotate();
				   temp = node.getParent().getLeft();
			   }
			   if ((temp.getRight().getColor() == "black") & (temp.getLeft().getColor() == "black")){
				   temp.setColor("red");
				   node = node.getParent(); 
			   }
			   else{
				   if (temp.getLeft().getColor() == "black"){
					   temp.getRight().setColor("black");
					   temp.setColor("red");
					   temp.leftRotate();
					   temp = node.getParent().getLeft();
				   }
				   temp.setColor(node.getParent().getColor());
				   node.getParent().setColor("black");
				   temp.getLeft().setColor("black");
				   node.getParent().rightRotate();
				   node = getRoot();			   
			   }
		   }
		   }
	   node.setColor("black");
	   }
   
   /**
    * public void delete(int i)
    * 
    * deletes the integer i from the binary tree; the tree
    * must remain valid (keep its invariants).
    * 
    * precondition:  contains(i) == true (that is, i is in the tree)
    * postcondition: contains(i) == false (that is, i is not in the tree)
    */
   public void delete(int i)
   {
	   RBNode y = new RBNode();  
	   RBNode x = new RBNode();   // x and y are temporary helping nodes
	   RBNode node = treeSearch(getRoot(), i);
	   
	   if ((node.getLeft().nullNode()) | (node.getRight().nullNode()))
		   y = node;
	   else y = treeSearch(this.getRoot(), succ(node.getKey()));
	   
	   if (!y.getLeft().nullNode())
		   x = y.getLeft();
	   else x = y.getRight();
	   
	   x.setParent(y.getParent());
	   
	   if (y.getParent().nullNode())
		   setRoot(x);
	   else{
		   if (y == y.getParent().getLeft())
			   y.getParent().setLeft(x);
		   else y.getParent().setRight(x);
	   }
	   
	   if (y != node)
		   node.setKey(y.getKey());
	   if (y.getColor() == "black")
		   RBDeleteFIXUP(x);
   }
   
   
   /**
    * public int min()
    * 
    * returns the smallest key in the tree. If the tree
    * is empty, returns -1.
    * 
    * precondition: none
    * postcondition: none
    */
   public int min()
   {
	   int key = -1;
	   RBNode temp = getRoot();
	
	   while ((!empty()) && (!temp.nullNode())){
		   key = temp.getKey();
		   temp = temp.getLeft();
		   }
	   return key;
   }
   
   
   /**
    * public int max()
    * 
    * returns the largest key in the tree. If the tree
    * is empty, returns -1.
    * 
    * precondition: none
    * postcondition: none
    */
   public int max()
   {
	   int key = -1;
	   RBNode temp = getRoot();
	
	   while ((!empty()) && (!temp.nullNode())){
		   key = temp.getKey();
		   temp = temp.getRight();
		   }
	   return key;
   }
   
   
   
   //returns the number of blacks from the node down including his color
   //checks the following:
   //if a node is red: checks that both its sons are black
   //if a node is a nullNode checks if it is black
   //checks the black height of the tree
   //if the tree is not legal will return -1
   //note: the tree implementation for a node's color is boolean
   //false represents black and true is red
   //therefore a node can't be in any other color
   public static int numberofblacks(RBNode tree){
		if (tree.nullNode())
			return 1;
		else {			
			int numleft = numberofblacks(tree.getLeft());
			int numright = numberofblacks(tree.getRight());
			if ((numleft==numright) & (numleft!=-1))     // the number of blacks is even and legal
				if (tree.getColor()=="black"){
					if (!tree.getLeft().nullNode())
						if (tree.getKey() <= tree.getKey())
							return -1;
					if (!tree.getRight().nullNode())
						if (tree.getKey() >= tree.getRight().getKey())
							return -1;					
					return (1+numleft);                    //both are legal and the node is black
				} else {                                   //the node is red so we check its sons
					if (!tree.getLeft().nullNode())
						if ((tree.getLeft().getColor() == "red") | (tree.getKey() <= tree.getLeft().getKey()))
							return -1;
					if (!tree.getRight().nullNode())
						if ((tree.getRight().getColor()=="red") | (tree.getKey() >= tree.getRight().getKey()))
							return -1;		
					return numleft;                      //both sons are black and legal, so it's legal
				}
			else                          //the sub trees are illegal
				return -1;
		}	
	}
   
   /**
    * public boolean isLegalRedBlackTree()
    * 
    * returns true if and only if the tree is a legal red-black tree.
    * 
    * preconditions: none
    * postconditions: none
    */
   public boolean isLegalRedBlackTree()
   {
	   if (numberofblacks(this.getRoot())>0)
			return true;
		else
			return false;
   }
   

   /**
    * public int pred(int i)
    * 
    * returns the predecessor of an element. If the element has
    * no predecessor, returns -1.
    * 
    * preconditions: contains(i) == true (that is, i is in the tree)
    * postconditions: none
    */
   public int pred(int i)
   {
	   RBNode node = treeSearch(getRoot(), i);
	   RBNode temp = new RBNode();
	   
	   if (!node.getLeft().nullNode()){
		   return node.getLeft().getMax().getKey();
	   }
	   temp = node.getParent();
	   
	   while ((!temp.nullNode()) && (node == temp.getLeft())){
		   node = temp;
		   temp = temp.getParent();
	   }
	   if (!temp.nullNode()) return temp.getKey();
	   else return -1;
   }
   
   
   /**
    * public int succ(int i)
    * 
    * returns the successor of an element. If the element has
    * no successor, returns -1.
    * 
    * preconditions: contains(i) == true (that is, i is in the tree)
    * postconditions: none
    */
   public int succ(int i)
   {
	   RBNode node = treeSearch(getRoot(), i);
	   RBNode temp = new RBNode();
	   
	   if (!node.getRight().nullNode()){
		   return node.getRight().getMin().getKey();
	   }
	   temp = node.getParent();
	   
	   while ((!temp.nullNode()) && (node == temp.getRight())){
		   node = temp;
		   temp = temp.getParent();
	   }
	   if (!temp.nullNode()) return temp.getKey();
	   else return -1;
   }


   //an iterative helping function for isComplete
   private static int isCompleteIter(RBNode node){
	   if (node.nullNode())
		   return 0;
	   else{
		   int left = isCompleteIter(node.getLeft());
		   int right = isCompleteIter(node.getRight());
		   if ((left==right) && (left!=-1))
			   return (left+1);
		   else
			   return -1;
	   }
   }
   
   
   /**
    * public boolean isComplete()
    * 
    * returns true if and only if the tree is a complete binary tree.
    * 
    * preconditions: none
    * postconditions: none
    */
   public boolean isComplete()
   {
	   if (isCompleteIter(this.getRoot())>=0)
		   return true;
	   else
		   return false;
   }
   
   
   //a method to count the number of nodes in the tree
   //goes over each node in the tree once
   //= O(n)
   //used in toIntArray()
   public  int numNodes(RBNode startNode){
	   if (startNode.nullNode())
		   return 0;
	   else
		   return (1 + numNodes(startNode.getLeft()) + numNodes(startNode.getRight()));
   }
   
   
   /**
    * public int[] toIntArray()
    * 
    * returns an int[] array containing the values stored in the tree,
    * in ascending order.
    * 
    * preconditions: none
    * postconditions: returns an array containing exactly the tree's elements in
    *                 ascending order.
    */
   public int[] toIntArray()
   {
	   int[] arr = new int[numNodes(this.getRoot())]; //
		  int minKey = min();	  
		  int i = 0;
		  
		  while (minKey != -1){
			  arr[i] = minKey;
			  minKey = succ(minKey);
			  i++;
		  }
		  return arr; 
   }
  
   
   /**
    * public class RBNode
    * 
    * If you wish to implement classes other than RBTree
    * (for example RBNode), do it in this file, not in 
    * another file 
    *  
    */
   public class RBNode{
	   
///////////////////////////////////////////////////////////////////////////////////////////
	   //RBNode is a node object containing the node's fields and methods
	   //also contains the left and right rotate methods
	   
	   
///////////////////////////////////// Node fields /////////////////////////////////////////
		private int Key;
		private boolean Color; // false is black , true is red
		private RBNode Parent;
		private RBNode LeftChild;
		private RBNode RightChild;
		
		
/////////////////////////////////////  Constructors getters & setters ///////////////////////
		
		
		//the basic node constructor, returns as default a nullNode if used
		public RBNode(){			
			this.Color = false;
			this.Parent = null;
			this.LeftChild = null;
			this.RightChild = null;
			this.Key = -7;     //an arbitrary number to represent a nullNode's key
		}
		
		public RBNode (RBNode father, RBNode leftson, RBNode rightson, int index, String nodecolor) { 
			this.Key = index;
			if (nodecolor.toLowerCase()=="red")
				this.Color = true;
			else
				this.Color = false;
			this.Parent = father;
			this.LeftChild = leftson;
			this.RightChild = rightson;
		}
		
		//checks if the node is a nullNode.
		public boolean nullNode(){
			if (this.getKey() == -7)
				return true;					
			else
				return false;
		}
		//checks if the node is the root of the tree
		public boolean isRoot(){
			return (this.getParent()==null);
		}
		
		//returns the color of the node as string (black/red)
		public String getColor(){
			if ((this == null) || (this.Color == false) || (this.getKey() == -7))
				return "black";
			else
				return "red";
		}
		
		//receives a node & "red" / "black" and sets the new color
		public void setColor(String color){
			if (color.toLowerCase()=="red")
				this.Color = true;
			else
				this.Color = false;
		}
		
		//returns the node's key
		public int getKey(){
			return this.Key;
		}
		
		//sets a new key for the node
		public void setKey(int newkey){
			this.Key = newkey;
		}
		
		//returns the parent node
		public RBNode getParent(){
			return this.Parent;
		}
		
		//sets the parent node
		public void setParent(RBNode newParent){
			this.Parent = newParent;
		}
		
		//returns the Grand-Father node. makes the code clearer
		public RBNode getGParent(){
			return this.getParent().getParent();
		}
		
		//sets the Grand-Father node
		public void setGParent(RBNode newGParent){
			this.getParent().setParent(newGParent);
		}
		
		//returns the left son node
		public RBNode getLeft(){
			return this.LeftChild;
		}
		
		//sets the left son node
		public void setLeft(RBNode newSon){
			this.LeftChild = newSon;
		}
		
		//returns the right son node
		public RBNode getRight(){
			return this.RightChild;
		}
		
		//sets the right son node
		public void setRight(RBNode newSon){
			this.RightChild = newSon;
		}
		
		//returns the root of the node
		public RBNode findRoot(){
			if (getParent().nullNode())
				return this;
			else
				return getParent().findRoot();
		}
		
		//////////////////////////// more elaborated fuctions //////////////////////////////
		
		//Left rotates the node
		// @pre: the left son != null
		public void rightRotate(){
			RBNode name = this.getLeft().getRight();
			RBNode son = this.getLeft();
			RBNode parent = this.getParent();
			
			son.setParent(parent);
			son.setRight(this);
			this.setParent(son);
			this.setLeft(name);
			if (!nullNode())
					name.setParent(this);
			if (!nullNode())
				if (son.getParent().getLeft() == this)	
					son.getParent().setLeft(son);
					
				else
					son.getParent().setRight(son);
		}
		
		//Right Rotates the node
		// @pre: the right son != null
		public void leftRotate(){
			RBNode node = this.getRight().getLeft();
			RBNode son = this.getRight();
			RBNode parent = this.getParent();
			
			son.setParent(parent);
			son.setLeft(this);
			this.setParent(son);
			this.setRight(node);
			if (!nullNode())
					node.setParent(this);
			if (!nullNode())
					if (son.getParent().getLeft() == this)
						son.getParent().setLeft(son);
					else
						son.getParent().setRight(son);
							
		}
		
		//returns the minimum value child of the node 
		public RBNode getMin(){
			RBNode node = this;

			while (!node.getLeft().nullNode()){
				node = node.getLeft();
			}
			return node;
		}
		
		//returns the maximum value child of the node
		public RBNode getMax(){
			RBNode node = this;

			while (!node.getRight().nullNode()){
				node = node.getRight();
			}
			return node;
		}
   }
  
}
/**
 * @original author Shai Vardi
 * @additions by Eran Matityahu
 */


  

